﻿using System;
using System.IO;

namespace luozhuangSLLZSS
{
   
        public class lz77
        {
            public lz77()
            {

            }

            #region 压缩数据
            public void zipData(Stream data, Stream zipedData)
            {
                /////////////////////////////////
                //       初始化变量
                /////////////////////////////////


                int p, wPos, wLen, tPos, tLen;
                int dataLength = (int)data.Length;
                int bufferLength = 0;
                byte[] buffer = new byte[4096];
                byte[] buffer_zip = new byte[8092];
                int[] nextSamePoint = new int[4096];
                int bufferDP;
                bool f, ff;
                byte tByteLen = 0;
                int tInt = 0;

                /////////////////////////////////
                //     开始分组压缩
                /////////////////////////////////

                while ((bufferLength = data.Read(buffer, 0, 4096)) > 0)
                {

                    // 如果buffer长度太短直接保存
                    if (bufferLength < 6)
                    {
                        for (int i = 0; i < Math.Min(3, bufferLength); i++)
                        {
                            tInt = (tInt << 8) + buffer[i];
                            zipedData.WriteByte((byte)(tInt >> tByteLen));
                            tInt = getRightByte(tInt, tByteLen);
                        }
                        for (int i = 3; i < bufferLength; i++)
                        {
                            tInt = (tInt << 9) + buffer[i];
                            tByteLen += 9;
                            while (tByteLen >= 8)
                            {
                                zipedData.WriteByte((byte)(tInt >> (tByteLen -= 8) << 24 >> 24));
                            }
                            tInt = getRightByte(tInt, tByteLen);  // 记录剩余信息
                        }
                        break;
                    }

                    // 提前计算出下一个相同字节的位置
                    for (int i = 0; i < bufferLength; i++)
                    {
                        for (int j = i + 1; j < bufferLength; j++)
                        {
                            nextSamePoint[i] = 4096;
                            if (buffer[i] == buffer[j])
                            {
                                nextSamePoint[i] = j;
                                break;
                            }
                        }
                    }

                    // 初始化字典和滑块
                    tInt = (tInt << 8) + buffer[0];
                    buffer_zip[0] = (byte)(tInt >> tByteLen);
                    tInt = getRightByte(tInt, tByteLen);

                    tInt = (tInt << 8) + buffer[1];
                    buffer_zip[1] = (byte)(tInt >> tByteLen);
                    tInt = getRightByte(tInt, tByteLen);

                    tInt = (tInt << 8) + buffer[2];
                    buffer_zip[2] = (byte)(tInt >> tByteLen);
                    tInt = getRightByte(tInt, tByteLen);

                    p = 3;
                    wPos = 0;
                    wLen = 3;
                    tPos = -1;
                    tLen = 0;
                    bufferDP = 2;

                    ////////////////////////////////
                    //        开始编码
                    ////////////////////////////////

                    while (bufferLength - 3 >= p)
                    {
                        while (wPos + wLen <= p && p + wLen <= bufferLength)
                        {
                            // 判断滑块是否匹配
                            f = true;
                            if (buffer[wPos] == buffer[p])
                            {
                                ff = true;
                                for (int i = 1; i < wLen; i++)
                                {
                                    if (buffer[wPos + i] != buffer[p + i])
                                    {
                                        f = false;
                                        break;
                                    }
                                }
                            }
                            else
                            {
                                f = false;
                                ff = false;
                            }

                            // 匹配则增加滑块长度，否则移动
                            if (!f)
                            {
                                // 滑块移动
                                if (ff)
                                {
                                    wPos = nextSamePoint[wPos];
                                }
                                else
                                {
                                    wPos++;
                                }
                            }
                            else
                            {
                                // 增加滑块长度
                                while (wPos + wLen != p && p + wLen != bufferLength && wLen < 1024)
                                {
                                    if (buffer[wPos + wLen] == buffer[p + wLen])
                                    {
                                        wLen++;
                                    }
                                    else
                                    {
                                        break;
                                    }
                                }
                                tPos = wPos;
                                tLen = wLen;

                                // 滑块移动并增加1长度
                                wPos = nextSamePoint[wPos];
                                wLen++;
                            }

                        }

                        //////////////////////////////////
                        //     写入buffer_zip
                        //////////////////////////////////

                        if (tPos == -1)
                        {
                            // 单个字节
                            tInt = (tInt << 9) + buffer[p];
                            tByteLen += 9;
                            p++;
                        }
                        else
                        {
                            // 匹配的字节串
                            tInt = (((tInt << 1) + 1 << 12) + tPos << 11) + tLen;
                            tByteLen += 24;
                            p += tLen;
                        }
                        while (tByteLen >= 8)
                        {
                            buffer_zip[++bufferDP] = (byte)(tInt >> (tByteLen -= 8) << 24 >> 24);
                        }
                        tInt = getRightByte(tInt, tByteLen);  // 记录剩余信息

                        ////////////////////////////////////
                        //        初始化滑块
                        ////////////////////////////////////

                        wPos = 0;
                        wLen = 3;
                        tPos = -1;
                        tLen = 0;
                    }

                    // 写入剩余字节
                    for (int i = p; i < bufferLength; i++)
                    {
                        tInt = (tInt << 9) + buffer[i];
                        tByteLen += 9;
                        buffer_zip[++bufferDP] = (byte)(tInt >> (tByteLen -= 8));
                        tInt = getRightByte(tInt, tByteLen);
                    }

                    // 写入Stream
                    zipedData.Write(buffer_zip, 0, bufferDP + 1);
                }

                if (tByteLen != 0) zipedData.WriteByte((byte)(tInt << 8 - tByteLen)); // 写入剩余信息
                data.Close();
                zipedData.Close();

            }
            #endregion

            #region 解压数据
            public void unzipData(Stream zipedData, Stream data)
            {
                /////////////////////////////////
                //       初始化变量
                /////////////////////////////////


                uint wPos = 0, wLen = 0;
                int buffer_zipLength = (int)zipedData.Length;
                byte[] buffer = new byte[4096];
                byte[] buffer_zip = new byte[buffer_zipLength];
                int buffer_zipDP = -1;
                int bufferDP = -1;
                byte tByteLen = 0;
                uint tInt = 0;
                zipedData.Read(buffer_zip, 0, buffer_zipLength);

                /////////////////////////////////
                //        开始解压
                /////////////////////////////////

                while (buffer_zipDP < buffer_zipLength - 3)
                {

                    // 写入前3个字节
                    tInt = (tInt << 8) + buffer_zip[++buffer_zipDP];
                    buffer[0] = (byte)(tInt >> tByteLen);
                    tInt = getRightByte(tInt, tByteLen);

                    tInt = (tInt << 8) + buffer_zip[++buffer_zipDP];
                    buffer[1] = (byte)(tInt >> tByteLen);
                    tInt = getRightByte(tInt, tByteLen);

                    tInt = (tInt << 8) + buffer_zip[++buffer_zipDP];
                    buffer[2] = (byte)(tInt >> tByteLen);
                    tInt = getRightByte(tInt, tByteLen);

                    bufferDP = 2;

                    while (bufferDP < 4095)
                    {
                        // 读入充足数据
                        while (tByteLen < 24 && buffer_zipDP < buffer_zipLength - 1)
                        {
                            tInt = (tInt << 8) + buffer_zip[++buffer_zipDP];
                            tByteLen += 8;
                        }

                        // 写入buffer
                        if (tInt >> tByteLen - 1 == 0)
                        {
                            // 单个字节
                            tByteLen -= 1;
                            tInt = getRightByte(tInt, tByteLen);
                            buffer[++bufferDP] = (byte)(tInt << 32 - tByteLen >> 24);
                            tByteLen -= 8;
                            tInt = getRightByte(tInt, tByteLen);
                        }
                        else
                        {
                            // 字节串
                            tByteLen -= 1;
                            tInt = getRightByte(tInt, tByteLen);
                            wPos = tInt >> (tByteLen -= 12);
                            tInt = getRightByte(tInt, tByteLen);
                            wLen = tInt >> (tByteLen -= 11);
                            tInt = getRightByte(tInt, tByteLen);
                            for (int i = 0; i < wLen; i++)
                            {
                                buffer[++bufferDP] = buffer[wPos + i];
                            }
                        }

                        // 判断是否解压完成
                        if (buffer_zipDP == buffer_zipLength - 1 && tByteLen < 9) break;

                    }

                    // 写入Stream
                    data.Write(buffer, 0, bufferDP + 1);
                }

                // 写入剩余的信息
                for (int i = buffer_zipDP + 1; i < buffer_zipLength; i++)
                {
                    data.WriteByte(buffer_zip[i]);
                }

                zipedData.Close();
                data.Close();

            }
            #endregion

            #region private item
            private int getLeftByte(int dataLine, int s)
            {
                return dataLine << 32 - s >> 24;
            }

            private static uint getLeftByte(uint dataLine, int s)
            {
                return dataLine << 32 - s >> 24;
            }

            private int getRightByte(int dataLine, int l)
            {
                if (l == 0)
                {
                    return 0;
                }
                else
                {
                    return dataLine << (32 - l) >> (32 - l);
                }
            }

            private uint getRightByte(uint dataLine, int l)
            {
                if (l == 0)
                {
                    return 0;
                }
                else
                {
                    return dataLine << (32 - l) >> (32 - l);
                }
            }
            #endregion
        } 
    
}
